package a04_字符串;

import java.util.Arrays;

/**
 * <p>
 * a06_实现strStr复习4
 * </p>
 *
 * @author flyduck
 * @since 2025/1/13
 */
public class a06_实现strStr复习4 {
    public static void main(String[] args) {
        a06_实现strStr复习4 test = new a06_实现strStr复习4();
//        int i = test.strStr("aabaabaaf", "aabaaf");
        int i = test.strStr("leetcode", "leeto");
        System.out.println(i);
    }
    public int strStr(String outStr, String inStr) {
        char[] inChars = inStr.toCharArray();
        char[] outChars = outStr.toCharArray();
        int[] nextArray = getNextArray(inChars);
        int inIdx = 0;
        int outIdx = 0;
        //aabaabaaf
        //   aabaaf
        //9 - 6
        while (inIdx < inChars.length && outIdx < outChars.length) {
            if(inChars[inIdx] == outChars[outIdx]){
                inIdx++;
                outIdx++;
            }else {
                inIdx = nextArray[inIdx];
                if(inIdx == -1){//说明第一个也不行
                    outIdx++;
                    inIdx = 0;
                }
            }
        }
        if(inIdx == inChars.length){
            return outIdx - inIdx;
        }else {
            return -1;
        }
    }

    private int[] getNextArray(char[] chars){
        if (chars.length == 1) {
            return new int[]{-1};
        }
        int[] nextArray = new int[chars.length];
        nextArray[0] = -1;
        nextArray[1] = 0;
        int currentIdx = 2;
        int compareIdx = nextArray[currentIdx - 1];
        //xxx a xxx ab
        //          3
        while (currentIdx < chars.length) {
            if(chars[currentIdx-1] == chars[compareIdx]){
                nextArray[currentIdx] = compareIdx + 1;
                currentIdx++;
                compareIdx = nextArray[currentIdx - 1];
            }else{
                if(compareIdx == 0){
                    nextArray[currentIdx] = 0;
                    currentIdx++;
                    compareIdx = nextArray[currentIdx - 1];
                }else{
                    compareIdx = nextArray[compareIdx];
                }
            }
        }
        return nextArray;
    }
}
